/// https://leetcode-cn.com/problems/search-insert-position
pub struct Solution;

impl Solution {
    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 1.9 MB , 在所有 Rust 提交中击败了 96.84% 的用户
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        match nums.binary_search(&target) {
            Ok(x) => x as i32,
            Err(x) => x as i32,
        }
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 1.9 MB , 在所有 Rust 提交中击败了 97.89% 的用户
    pub fn search_insert_iter(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len() as i32;
        nums.into_iter()
            .enumerate()
            .find(|&(_, x)| x >= target)
            .map(|(i, _)| i as i32)
            .unwrap_or(n)
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2 MB , 在所有 Rust 提交中击败了 69.47% 的用户
    pub fn search_insert_dichotomy(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        if n == 0 || target <= nums[0] {
            0
        } else if target > nums[n - 1] {
            n as i32
        } else {
            let (mut i, mut mid, mut j) = (0, n / 2, n - 1);
            while i <= j {
                if target < nums[mid] {
                    j = mid - 1;
                } else if target > nums[mid] {
                    i = mid + 1;
                } else {
                    return mid as i32;
                }
                mid = (i + j) / 2;
            }
            return if target > nums[mid] { mid as i32 + 1 } else { mid as i32 };
        }
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2 MB , 在所有 Rust 提交中击败了 86.32% 的用户
    pub fn search_insert_dichotomy2(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        if n == 0 || target <= nums[0] {
            0
        } else if target > nums[n - 1] {
            n as i32
        } else {
            let (mut i, mut ans, mut j) = (0, n, n - 1);
            let mut mid;
            // println!("\n{} {}", "-".repeat(30), target);
            while i <= j {
                mid = (i + j) / 2;
                // vec_pos!(nums; i=i, k=mid, j=j);
                if target <= nums[mid] {
                    ans = mid;
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            }
            ans as i32
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert(f: impl Fn(Vec<i32>, i32) -> i32) {
        assert_eq!(f(vec![1, 3, 5, 6], 5), 2);
        assert_eq!(f(vec![1, 3, 5, 6], 2), 1);
        assert_eq!(f(vec![1, 3, 5, 6], 4), 2);
        assert_eq!(f(vec![1, 3, 5, 6], 7), 4);
        assert_eq!(f(vec![1, 3, 5, 6], 0), 0);
        assert_eq!(f(vec![1, 3], 2), 1);
        assert_eq!(f(vec![1, 3], 3), 1);
    }

    bench!(assert Solution::search_insert);
    bench!(assert Solution::search_insert_iter);
    bench!(assert Solution::search_insert_dichotomy);
    bench!(assert Solution::search_insert_dichotomy2);
}
